The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
In the network, some nodes represent end systems (such as printers, fax machines, telephones, PC's etc) whereas other nodes represent network devices (e.g. switches, routers etc). The data packets are sent around the network from a source to a destination in accordance for example with routing information shared among the nodes of the network. As the network comprises a plurality of interconnected nodes, the network is fairly robust. Should a node or link fail for any reason, the network dynamically configures to re-route data so as to avoid the failed node. When a node or link comes into existence on a network, for instance through repair or by addition of a new node, the network dynamically converges to a so-called converged state wherein all the routers of the network have common routing information.
One class of routing protocols that rely on shared information is the link state protocol. Examples of link state protocols are the Intermediate System-to-Intermediate System (IS-IS) protocol and the Open Shortest Path First (OSPF) protocol. The IS-IS protocol is specified in ISO 10589, with extensions for supporting IPv4 specified in RFC 1195.
A link state protocol relies on a routing algorithm resident at each node of a network. Each node of the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link that can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA.
Based on the advertised information in the form of a link state packet (LSP), each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node. A link can be thought of as an interface on a router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface may include, for example, the IP address of the interface, the mask, the type of network it is connected to, the router connected to that network and so on. The collection of all link states for the whole network forms the link-state database.
Each LSP is composed of a fixed header and a number of tuples, each consisting of a type, a length, and a value. Such tuples are commonly referred to as TLVs. Specialized tuples may also be used, which are referred to as sub-TLVs. TLVs and sub-TLVs may be used to encode information in a flexible and extensible format.
Link state protocols use a link state algorithm to build and calculate the shortest path to all known destinations. The algorithms for determining a shortest path are complicated but the following provides a simplified view of the steps of a link state algorithm. Upon initialization or due to any changing routing information, a router generates an advertisement LSP. This advertisement represents the collection of all link states on that router. All routers exchange LSPs by means of flooding. Each router that receives a link state update stores a copy in its link state database and then rapidly propagates the update to other routers. After the database of each router is completed, each router calculates the shortest (lowest cost) path to all designations and uses this information to form an IP routing table. In some instances two or more routers of equal cost present themselves, termed an “equal cost path split.” One appropriate algorithm is a shortest path first (SPF) algorithm.
As a result, a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Conversely, a “reverse spanning tree” can be constructed showing the optimum path to a given node from all nodes from which it is reachable. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning and reverse spanning tree rooted at any other node. The results of the SPF are stored in a routing table (also known as a routing information base (RIB)) and, based on these results, the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately.
In link state protocols, when a link or a node fails and is subsequently repaired, or there is some other change to the network such as a change of link cost, the routers involved with the repaired part of the network then have to re-establish convergence. This is achieved by the router(s) advertising themselves or the change throughout the network area. However, during topology change, there is a short period of time in which LSDBs, RIBs and FIBs across a network become inconsistent as information about a change is propagated through the network. Routes generated during this period of inconsistency may result in routing loops, which persist until the databases have converged, at which point there should be no loops, by definition. Consequently, it is advantageous to minimize the amount of time necessary for a set of routers to achieve convergence, which is the time when the LSDBs, RIBs and FIBs of the routers involved are consistent which each other.
As explained above, the IS-IS protocol may be used to carry routing information. Routing information, as used herein, refers to information describing the link state of a link of a network used in converging the nodes of a network. For example, the routers of a network may exchange routing information to ensure that each router's LSDBs, RIBs and FIBs are consistent which each other.
In recent years, many extensions have been made to the IS-IS protocol to allow IS-IS packets (packets that conform to the IS-IS protocol) to carry non-routing information in addition to routing information. Non-routing information, as used herein, refers to information that does not qualify as routing information, which may be used to provide additional services beyond that of strictly routing packets. For example, non-routing information may be used by a multi-protocol label switching-traffic engineering (MPLS-TE) component of a router in order to create, signal, and establish TE tunnels. Non-routing information may include Traffic Engineering (TE) information. TE information describes the resources associated with each link, e.g., TE information may describe the available bandwidth not being consumed on a particular link. Thus, an IS-IS packet may carry both routing information and non-routing information in TLVs and sub-TLVs.
With the increase of MPLS-TE development and deployment, IS-IS packets are carrying more non-routing information, especially TE information. When a router receives a new LSP, the router determines if the state of any links in the network has changed, e.g., a new link may be available or a particular link may be unavailable. This determination requires that the router read, parse, and process all information contained within each TLV and sub-TLV in the LSP, including any non-routing information, even though the non-routing information is not used in updating a router's LSDBs, RIBs and FIBs. As a result, the time it takes for routers of the network to achieve convergence may be increased beyond an acceptable threshold, and the performance of the router is negatively impacted.
Based on the foregoing, there is a clear need for an improved method for the dissemination of non-routing information to nodes of a network.